<BODY>
<P> Provides high-performance collection classes and miscellaneous utilities; although 
    this package provides very few collection classes, they are substitutes for
    most of <code>java.util.*</code> classes (for example, <code>java.util.IdentityHashMap</code> would be 
    a {@link javolution.util.FastMap FastMap} with an {@link javolution.util.FastComparator#IDENTITY
    identity} key comparator).</P>

<h2><a name="OVERVIEW">Overview:</a></h2>

<P> <b>J</b>avolution collections are compliant with standard collections 
    (generic when built with the ant target <code>1.5</code>) and they can <b>safely</b> be used 
    with <a href="http://www.rtj.org/">RTSJ</a> virtual machines (e.g. if the capacity of 
    a collection increases, the extension part is allocated from the same memory 
    area as the collection itself).</P>

<P> They support direct iterations with the following advantages:
    <UL>
    <LI>Faster than iterators, see <A href="http://javolution.org/doc/benchmark.html">benchmark</A>.</LI>
    <LI>No object creation not even the iterator object itself. For example, visiting a tree structure using
        iterators creates as many iterators as they are nodes in the tree:[code]
    public static void visit(Collection<Collection> node) {
        for (Collection<Collection> i : node) { // Creates iterator.
            visit(i);
        }
    }[/code]
    Not so with direct iterations:[code]
    public static void visit(FastCollection<FastCollection> node) {
        for (FastCollection.Record r = node.head(), end = node.tail(); (r = r.getNext()) != end;) {
            visit(node.valueOf(r));
        }
    }[/code]</LI>
    <LI>Used to implement most of {@link javolution.util.FastCollection FastCollection} base class methods 
        (including {@link javolution.util.FastCollection#iterator iterator()}).</LI>
    <LI>Support forward/backward iterations from the start (head) or from the end (tail)</LI>
    <LI>Thread-safe as long as objects are not inserted/removed during iterations. Objects can safely be 
       append/prepend by the current thread or other threads.
        <i>(Note: {@link javolution.util.FastMap#setShared Shared FastMap} are always thread-safe even when entries are removed)</i>.</LI>
    <LI>Fully integrated with the JDK1.5+ generic framework (strong typing) and still compatible 
        with other platforms (J2ME, 1.4, GCJ).</LI>
    </UL>
    Here are few examples of direct iterations:[code]
    FastList<String> list;
    for (FastList.Node<String> n = list.head(), end = list.tail(); (n = n.getNext()) != end;) {
        String value = n.getValue(); // No typecast necessary.    
    }
    ...
    FastMap<String, Thread> map;
    for (FastMap.Entry<String, Thread> e = map.head(), end = map.tail(); (e = e.getNext()) != end;) {
        String key = e.getKey(); // No typecast necessary.
        Thread value = e.getValue(); // No typecast necessary.
    }[/code]</P>

<P> Users may provide a read-only view of any {@link javolution.util.FastCollection FastCollection} 
    (or {@link javolution.util.FastMap FastMap}) instance using the 
    {@link javolution.util.FastCollection#unmodifiable() FastCollection.unmodifiable()}
    (or {@link javolution.util.FastMap#unmodifiable FastMap.unmodifiable()}) method.
     For example:[code]
    public class Polynomial {
       
        private final FastSet<Term> _terms = new FastSet<Term>();

        // Read-only view (also thread-safe as terms are not "deleted").
        public Set<Term> getTerms() { 
            return _terms.unmodifiable();
        }
    }[/code]</P>

<P> Collection/maps of primitive types can be created using the
    {@link javolution.util.Index Index} class. It avoids the overhead 
    of wrapping primitives types (for reasonably small <code>int</code> values).
    For example:[code]
    public class SparseVector<F> {
        FastMap<Index, F> _elements = new FastMap<Index, F>();
        ...
   }[/code] </P>

<P> Although all collections capacity increases smoothly (no resizing/copy or rehashing ever performed),
    it is nevertheless possible to specify an initial capacity; in which case, all necessary storage
    is allocated at creation. For <a href="http://www.rtj.org/">RTSJ</a> VMs, all 
    collections/maps can reside in <code>ImmortalMemory</code> (e.g. <code>static</code>)
    and be used by all threads (including <code>NoHeapRealtimeThread</code>) <b>without resulting into memory leaks 
    or illegal access errors</b>. For example:[code]
    public class XmlFormat {
        // RTSJ Unsafe! Memory leaks (when entries removed) or IllegalAssignmentError (when new entries while in ScopedArea).   
        static HashMap<Class, XmlFormat> ClassToFormat = HashMap<Class, XmlFormat>();
        
       // RTSJ Safe! Removed entries are internally recycled, new entries are in ImmortalMemory.
       static FastMap<Class, XmlFormat> ClassToFormat = FastMap<Class, XmlFormat>();
   }[/code]        
    For more details, please read <a href="http://javolution.org/doc/Javolution-Collections.pdf">Javolution-Collection.pdf</a></P>.  
     
<P> Temporary collection classes can be recycled (e.g. throw-away collections) to avoid the creation
    cost. For example:[code]
    static void removeDuplicate(List<Person> persons) {
        FastSet<Person> tmp = FastSet.newInstance(); // Possibly recycled instance.
        tmp.addAll(persons);
        persons.clear();
        persons.addAll(tmp);
        FastSet.recycle(tmp); // Recycles the temporary instance.
   }[/code]</p>  
 
<P> Here is a summary of the collection classes with their defining characteristics:
       <TABLE border="1" summary="Fast Collections Classes">
            <CAPTION><EM><B>Javolution Collections Classes</B></EM></CAPTION>
            <TR>
              <TD></TD>
              <TD><B>Ordering</B></TD>
              <TD><B>Duplication Allowed</B></TD>
              <TD><B>Custom Comparators</B></TD>
              <TD><B>Record Type</B></TD>
              <TD><B>Miscellaneous</B></TD>
            </TR>
            <TR>
              <TD>{@link javolution.util.FastTable FastTable}</TD>
              <TD>Insertion Order</TD>
              <TD>Yes</TD>
              <TD>{@link javolution.util.FastTable#setValueComparator setValueComparator(FastComparator)}</TD>
              <TD>{@link javolution.util.Index Index}</TD>
              <TD>Thread-safe random access collection<BR>
                  No array resize/copy ever performed</TD>
            </TR>
            <TR>
              <TD>{@link javolution.util.FastList FastList}</TD>
              <TD>Insertion Order</TD>
              <TD>Yes</TD>
              <TD>{@link javolution.util.FastList#setValueComparator setValueComparator(FastComparator)}</TD>
              <TD>{@link javolution.util.FastList.Node Node}</TD>
              <TD> Recycle their own nodes (no adverse effect on GC)</TD>
            </TR>
            <TR>
              <TD>{@link javolution.util.FastSet FastSet}</TD>
              <TD>Insertion Order</TD>
              <TD>No</TD>
              <TD>{@link javolution.util.FastSet#setValueComparator setValueComparator(FastComparator)}</TD>
              <TD>{@link javolution.util.FastCollection.Record Record}</TD>
              <TD>Based on {@link javolution.util.FastSet FastMap} (same characteristics)</TD>
            </TR>
            <TR>
              <TD><CODE>FastTree</CODE></TD>
              <TD>Comparator</TD>
              <TD>No</TD>
              <TD><CODE>setValueComparator(FastComparator)</CODE></TD>
              <TD><CODE>TreeNode</CODE></TD>
              <TD><I>(not implemented)</I></TD>
            </TR>
            <TR>
              <TD>{@link javolution.util.FastMap FastMap}</TD>
              <TD>Insertion Order</TD>
              <TD>Key: No<BR>Value: Yes</TD>
              <TD>{@link javolution.util.FastMap#setKeyComparator setKeyComparator(FastComparator)}<BR>
                  {@link javolution.util.FastMap#setValueComparator setValueComparator(FastComparator)}</TD>
              <TD>{@link javolution.util.FastMap.Entry Entry}</TD>
              <TD>Thread-safe when marked as {@link javolution.util.FastMap#setShared shared}<BR>
                  No rehash/resize ever performed <BR>
                  Recycle their own entries (no adverse effect on GC)</TD>
            </TR>
         </TABLE>
    </P>    
    
<h2><a name="FAQ">FAQ:</a></h2>
<ol>
    <li><b>ArrayList may throw ConcurrentModificationException,
           but <b>J</b>avolution FastTable does not, why?</b>
    <p> FastTable (or any <b>J</b>avolution collection/map) <b>do support concurrent modifications</b>
    as long as these are not insertions at an arbitrary position or deletions <i>(Note: Shared FastMap 
    <b>does</b> support concurrent deletions)</i>. 
    In other words you can safely iterate (using iterators or not) through a FastList, FastMap 
    (entries, keys values), FastTable, etc. while new elements/entries are being added 
    (by you or another thread). You can also export a {@link javolution.util.FastCollection#unmodifiable() read-only}
     view over your collection and still add more elements to it.</p>
    
    <p><i> Disallowing concurrent modifications (standard java util) has proven to be a performance 
    killer for many (forcing users to work with copies of their whole collections). Furthermore the additional checks required
    directly impact performance (e.g. ArrayList iterations about 3x slower than FastTable iterations).</i></p>
    </li>
    
    <li><b>Do you have a test case showing any scenario of concurrent modification where 
          ArrayList "fails" and FastTable doesn't?</b>
    <p> Let's say that you have a collection of "Units", and you want to provide users 
        with a read-only view of these units. The following code will fail miserably:[code]
    public class Unit {
        static ArrayList<Unit> INSTANCES = new ArrayList<unit>();
        public static List<Unit> getInstances() {
            return Collections.unmodifiableList(INSTANCES);
         }
    }[/code]
        Why? Because, it the user iterates on the read-only list of units while a new unit is added
        to the collection (by another thread) a <code>ConcurrentModificationException</code> is 
        automatically raised. In other words, it is almost impossible to provide a "read-only" view
        of non-fixed size collections with the current java.util classes (e.g. you will have to replace
        the whole collection each time a new unit is added).</p>
    <p> Now with FastTable the following is completely safe even when new units are added:[code]
    public class Unit {
        static FastTable<Unit> INSTANCES = new FastTable<unit>();
        public static List<Unit> getInstances() {
            return INSTANCES.unmodifiable();
        }
    }[/code]</p>
    </li>
        
    <li><b>Do checks for concurrent modifications make your code safer?</b>
    <p> Not really. The current checks for concurrent modifications do not "guarantee" that concurrent 
    modifications will not occur! You can imagine two threads one updating a collection
    and the other one iterating the collection. As long as the update is not performed 
    while the other thread is iterating, everything is fine (no ConcurrentModificationException)!
    But, if for a reason or another the timing changes (e.g. in the user environment) and 
    iterations are performed at the wrong time then your application crashes...
    Not a good thing and very high probability for this to happen!</p>
    </li>

    <li><b> Are {@link javolution.util.FastMap#setShared shared maps} valid substitutes for 
           <code>ConcurrentHashMap</code>?</b>
       <p> Unlike <code>ConcurrentHashMap</code> access to a
           shared FastMap never blocks. Retrieval reflects the map state not older than the last 
           time the accessing threads have been synchronized<sup><b>*</b></sup> (for multi-processors
           systems synchronizing ensures that the CPU internal cache is not stale).</p>
           
       <p> In practice, it means that <b>most well-written</b> concurrent programs should 
           be able to use shared FastMap in place of <code>ConcurrentHashMap</code> as 
           threads are already synchronized to ensure proper behavior.</p>
           
       <p> <sup><b>*</b></sup> It is important for both threads to synchronize on the same monitor
          in order to set up the happens-before relationship properly. It is not the case 
          that everything visible to thread A when it synchronizes on object X becomes visible
          to thread B after it synchronizes on object Y. The release and acquire have to
          "match" (i.e., be performed on the same monitor) to have the right semantics.
          Otherwise, the code has a data race.</p>
           
    </li>
    
    <li><b>Are all <b>J</b>avolution collection thread-safe?</b>
    <p> Collections/Maps are thread-safe with regard to access (no need to
        synchronize reading even if the collection is modified concurrently).
        But the modifications themselves require either the collection/map to be
        marked shared or synchronization to be used.</p></li>
    
    <li><b>What is the overhead in term of performance when <code>FastMap.setShared</code>
           is set to <code>true</code>?</b>
    <p> Marking the map shared avoid synchronizing when possible (e.g. put when
        entry already exists or remove when entry does not exist), if a new entry
        is created and added, synchronization is performed internally. In all
        cases there is no impact on reading (never synchronized).</p></li>
</ol>
</BODY>